package _06_动态规划;

import java.util.Arrays;
import java.util.Comparator;

public class 剑指OfferII103最少的硬币数目 {

    public static void main(String[] args) {
        System.out.println(Integer.MAX_VALUE);
        System.out.println((long) Integer.MAX_VALUE + 1);
        剑指OfferII103最少的硬币数目 v = new 剑指OfferII103最少的硬币数目();
        int[] coins = new int[]{1, 2, 5};
        System.out.println(v.coinChange(coins, 11));
    }

    public int coinChange(int[] coins, int amount) {
        // 凑成i枚硬币们需要的最小数量
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE >> 1);
        dp[0] = 0;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
        return dp[amount] == Integer.MAX_VALUE >> 1 ? -1 : dp[amount];
    }

    public int coinChange2(int[] coins, int amount) {
        // 凑成i枚硬币们需要的最小数量
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE >> 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i < coin) continue;
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
        return dp[amount] == Integer.MAX_VALUE >> 1 ? -1 : dp[amount];
    }

    public int coinChange1(int[] coins, int amount) {
        if (amount == 0) return 0;
        // dp表示需要凑得i枚硬币，需要的最小硬币数
        long[] dp = new long[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        for (int i = 1; i <= amount; i++) {
            boolean find = false;
            // 查找当前coins中，是否有对应的硬币
            for (int coin : coins) {
                if (coin == i) {
                    dp[i] = 1;
                    find = true;
                    break;
                }
            }
            if (!find) {
                // 获取分配值
                int end = i >> 1;
                int j = 1;
                long minCoin = Integer.MAX_VALUE;
                while (j <= end) {
                    minCoin = Math.min(minCoin, dp[j] + dp[i - j]);
                    j++;
                }
                dp[i] = minCoin;
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : (int) dp[amount];
    }

}
